package leetcode_100;

import java.util.ArrayList;
import java.util.List;


/**
 *@author 周杨
 *UniqueBinarySearchTreesII_95 给定一个n 输出所有以1-n整数为值的二叉搜索树
 *describe:用动态规划的方式解决  AC 76%
 *	1. 每一次都在一个范围内随机选取一个结点作为根。 
	2. 每选取一个结点作为根，就把树切分成左右两个子树，直至该结点左右子树为空。

大致思路如上，可以看出这也是一个可以划分成子问题求解的题目，所以考点是动态规划。 
但具体对于本题来说，采取的是自底向上的求解过程。 
1. 选出根结点后应该先分别求解该根的左右子树集合，也就是根的左子树有若干种，它们组成左子树集合，根的右子树有若干种，它们组成右子树集合。 
2. 然后将左右子树相互配对，每一个左子树都与所有右子树匹配，每一个右子树都与所有的左子树匹配。然后将两个子树插在根结点上。 
3. 最后，把根结点放入链表中。
 *2018年5月19日 下午12:11:26
 */
public class UniqueBinarySearchTreesII_95 {
	List<TreeNode> res;
	boolean judge[];
	int count;
	int n;
	static class TreeNode{
		int val;
		TreeNode left;
		TreeNode right;
		TreeNode(int x) { val = x; }
	}
	public static void main(String[] args) {
		UniqueBinarySearchTreesII_95 test=new UniqueBinarySearchTreesII_95();
		//test.generateTrees(3);
		test.generateTrees1(4);

	}
	 public List<TreeNode> generateTrees1(int n) {
	        if(n < 1)
	            return new ArrayList<TreeNode>();
	        return helper1(1, n);
	    }
	
	
	/**
	 * describe:用动态规划的方法
	 * 2018年5月19日 下午12:02:39
	 * List<TreeNode>
	 */
	public List<TreeNode> helper1(int start, int end) {
        List<TreeNode> res = new ArrayList<TreeNode>();
        if(start > end) {
            res.add(null);
            return res;
        }
        for(int i = start; i <= end; i ++) {//在该范围内选取某一个数
            List<TreeNode> leftChild = helper1(start, i - 1);
            List<TreeNode> rightChild = helper1(i + 1, end);
            for(TreeNode left : leftChild) {
                for(TreeNode right : rightChild) {
                    TreeNode root = new TreeNode(i);
                    root.left = left;
                    root.right = right;
                    res.add(root);
                }
            }
        }
        return res;
    }
	
	
	/**
	 * describe: 假设当前有N个节点 则有n种方法选取根  每种选完根 再有N-1种动归数量选取下一个根 
	 * 从处理子问题的角度来看，选取一个结点为根，就把结点切成左右子树，以这个结点为根的可行二叉树数量就是左右子树可行二叉树数量的乘积，
	 * 所以总的数量是将以所有结点为根的可行结果累加起来。  
	 * 思想错误了 因为用回溯并不能让其遍历完左子树再遍历右子树
	 * 2018年5月19日 上午9:51:06
	 */
	public List<TreeNode> generateTrees(int n) {
		this.res=new ArrayList<TreeNode>();
		this.judge=new boolean[n+1];
		this.count=1;
		this.n=n;
		for(int i=1;i<=n;++i) {
			TreeNode head=new TreeNode(i);
			judge[i]=true;
			this.count=1;
			help(head,head,0,n+1);
			judge[i]=false;
		}
	    return this.res;
	}
	
	
	/**
	 * describe: 构造比left大 比right小的二叉树 
	 * 2018年5月19日 上午10:26:48
	 * @param left
	 * @param right
	 */
	public void help(TreeNode head,TreeNode root,int left,int right) {
		if(this.count==n) {
			TreeNode newNode=copyTree(head);
			this.res.add(newNode);
			return;
		}
		for(int i=left+1;i<root.val;++i) {//为其选择左子树
			if(!judge[i]) {
				if(i!=left+1){
					judge[i-1]=false;
					--count;//先回退刚才的	
				}
				root.left=new TreeNode(i);
				judge[i]=true;
				++count;
				help(head,root.left,left,root.val);//这棵子树不会最大不会超过i
			}					
		}
		for(int i=root.val+1;i<right;++i) {//为其选择右子树
			if(!judge[i]) {
				if(i!=root.val+1){
					judge[i-1]=false;
					--count;//先回退刚才的	
				}
				root.right=new TreeNode(i);
				judge[i]=true;
				++count;
				help(head,root.right,root.val,right);//这棵子树不会最小不会低于i

			}					
		}
		if(root.left!=null) {//需要回退左子树
			judge[root.left.val]=false;
			root.left=null;
			--count;
		}
		if(root.right!=null) {//需要回退右子树
			judge[root.right.val]=false;
			root.right=null;
			--count;
		}
	}
	
	public TreeNode copyTree(TreeNode root) {
		if(root!=null) {
			TreeNode node=new TreeNode(root.val);
			node.left=copyTree(root.left);
			node.right=copyTree(root.right);
			return node;
		}
		return null;
	}

}
